package com.tim.test.leetcode;

import org.junit.Test;

/**
 * @author
 * @Title:
 * @Package
 * @date 2023/6/11 22:44
 * @Description:
 */
public class Answer3 {

    @Test
    public void test(){
//        char[][] grid = new char[][]{
//                {'1','1','1','1','0'},
//                {'1','1','0','1','0'},
//                {'1','1','0','0','0'},
//                {'0','0','0','0','0'}
//        };
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println(numIslands(grid));;


    }

    /**
     * 200，岛屿数量
     * dfs，遍历全部节点。
     *  当前节点为0、2；直接返回
     *  遍历后，如为岛屿，置为2
     *  相邻节点无2，岛屿数量+1
     *  遍历相邻节点
     */
    int num = 0;
    public int numIslands(char[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                handleNode(grid, i, j);
            }
        }
        return num;
    }

    private void handleNode(char[][] grid, int i, int j) {
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length){
            return;
        }
        while(grid[i][j]=='1'){
            // 从左至右，从上到下遍历
            boolean flag = true;
            if(i >0){
                flag = grid[i-1][j]!='2';
            }
            if(flag && i +1< grid.length){
                flag = grid[i+1][j]!='2';
            }
            if(flag && j >0){
                flag = grid[i][j-1]!='2';
            }
            if(flag && j +1< grid[0].length){
                flag = grid[i][j+1]!='2';
            }
            if(flag){
                num++;
            }
            grid[i][j]='2';
            // 遍历相邻节点
            handleNode(grid, i-1, j);
            handleNode(grid, i+1, j);
            handleNode(grid, i, j-1);
            handleNode(grid, i, j+1);
        }
    }

}
